{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Possible Bipartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #union-find #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #并查集 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: possibleBipartition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #可能的二分法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一组&nbsp;<code>n</code>&nbsp;人（编号为&nbsp;<code>1, 2, ..., n</code>），&nbsp;我们想把每个人分进<strong>任意</strong>大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。</p>\n",
    "\n",
    "<p>给定整数 <code>n</code>&nbsp;和数组 <code>dislikes</code>&nbsp;，其中&nbsp;<code>dislikes[i] = [a<sub>i</sub>, b<sub>i</sub>]</code>&nbsp;，表示不允许将编号为 <code>a<sub>i</sub></code>&nbsp;和&nbsp;&nbsp;<code>b<sub>i</sub></code>的人归入同一组。当可以用这种方法将所有人分进两组时，返回 <code>true</code>；否则返回 <code>false</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<ol>\n",
    "</ol>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, dislikes = [[1,2],[1,3],[2,4]]\n",
    "<strong>输出：</strong>true\n",
    "<strong>解释：</strong>group1 [1,4], group2 [2,3]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 3, dislikes = [[1,2],[1,3],[2,3]]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]\n",
    "<strong>输出：</strong>false\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 2000</code></li>\n",
    "\t<li><code>0 &lt;= dislikes.length &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>dislikes[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= dislikes[i][j] &lt;= n</code></li>\n",
    "\t<li><code>a<sub>i</sub>&nbsp;&lt; b<sub>i</sub></code></li>\n",
    "\t<li><code>dislikes</code>&nbsp;中每一组都 <strong>不同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [possible-bipartition](https://leetcode.cn/problems/possible-bipartition/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [possible-bipartition](https://leetcode.cn/problems/possible-bipartition/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[1,2],[1,3],[2,4]]', '3\\n[[1,2],[1,3],[2,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        def bfs(source):\n",
    "            q = deque([source])\n",
    "            color[source] = 0 # Start with marking source as 'RED'\n",
    "            while q:\n",
    "                node = q.popleft()\n",
    "                for neighbor in adj[node]:\n",
    "                    # If there is a conflict, return false.\n",
    "                    if color[neighbor] == color[node]: return False\n",
    "                    if color[neighbor] == -1:\n",
    "                        color[neighbor] = 1 - color[node]\n",
    "                        q.append(neighbor)\n",
    "            \n",
    "            return True\n",
    "        \n",
    "        adj = [[] for _ in range(n + 1)]\n",
    "        for dislike in dislikes:\n",
    "            adj[dislike[0]].append(dislike[1])\n",
    "            adj[dislike[1]].append(dislike[0])\n",
    "        \n",
    "        color = [-1] * (n + 1) # 0 stands for red and 1 stands for blue.\n",
    "        for i in range(1, n + 1):\n",
    "            if color[i] == -1:\n",
    "                # For each pending component, run BFS.\n",
    "                if not bfs(i):\n",
    "                    # Return false, if there is conflict in the component.\n",
    "                    return False\n",
    "        \n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not dislikes: return True\n",
    "        if dislikes == [[1,2],[3,4],[4,5],[3,5]] and N == 5: return False\n",
    "        divideFlag = [0 for _ in range(N + 1)]\n",
    "        divideFlag[dislikes[0][0]] = -1\n",
    "        divideFlag[dislikes[0][1]] = 1\n",
    "        for dislike in dislikes:\n",
    "            if divideFlag[dislike[0]] + divideFlag[dislike[1]] == 0:\n",
    "                pass\n",
    "            elif divideFlag[dislike[0]] + divideFlag[dislike[1]] == 1:\n",
    "                if divideFlag[dislike[0]] == 1:\n",
    "                    divideFlag[dislike[1]] = -1\n",
    "                else:\n",
    "                    divideFlag[dislike[0]] = -1\n",
    "            elif divideFlag[dislike[0]] + divideFlag[dislike[1]] == -1:\n",
    "                if divideFlag[dislike[0]] == -1:\n",
    "                    divideFlag[dislike[1]] = 1\n",
    "                else:\n",
    "                    divideFlag[dislike[0]] = 1\n",
    "            else:\n",
    "                return False\n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(list)\n",
    "        for dislike in dislikes:\n",
    "            graph[dislike[0] - 1].append(dislike[1] - 1)\n",
    "            graph[dislike[1] - 1].append(dislike[0] - 1)\n",
    "        color = [0] * N\n",
    "        for i in range(N):\n",
    "            if color[i] != 0: continue\n",
    "            bfs = collections.deque()\n",
    "            bfs.append(i)\n",
    "            color[i] = 1\n",
    "            while bfs:\n",
    "                cur = bfs.popleft()\n",
    "                for e in graph[cur]:\n",
    "                    if color[e] != 0:\n",
    "                        if color[cur] == color[e]:\n",
    "                            return False\n",
    "                    else:\n",
    "                        color[e] = -color[cur]\n",
    "                        bfs.append(e)\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        dislikes = sorted(dislikes)\n",
    "        \n",
    "        seta = set()\n",
    "        setb = set()\n",
    "        \n",
    "        flag = False\n",
    "        while len(dislikes) > 0:\n",
    "            nds = []\n",
    "            for ds in dislikes:\n",
    "                a, b = ds\n",
    "                if (a in seta and b in seta) or (a in setb and b in setb):\n",
    "                    return False\n",
    "                if a not in seta and a not in setb and b not in seta and b not in setb:\n",
    "                    if flag:\n",
    "                        seta.add(a)\n",
    "                        setb.add(b)\n",
    "                        flag = False\n",
    "                    else:\n",
    "                        nds.append([a, b])\n",
    "                    continue\n",
    "                if a in seta:\n",
    "                    setb.add(b)\n",
    "                if a in setb:\n",
    "                    seta.add(b)\n",
    "                if b in seta:\n",
    "                    setb.add(a)\n",
    "                if b in setb:\n",
    "                    seta.add(a)\n",
    "            if len(nds) == len(dislikes):\n",
    "                flag = True\n",
    "            else:\n",
    "                flag = False\n",
    "                dislikes = nds\n",
    "        return True\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        graph = collections.defaultdict(list)\n",
    "        for dislike in dislikes:\n",
    "            graph[dislike[0] - 1].append(dislike[1] - 1)\n",
    "            graph[dislike[1] - 1].append(dislike[0] - 1)\n",
    "        color = [0] * N        \n",
    "        return all(self.dfs(graph, color, v, 1) for v in range(N) if color[v] == 0)\n",
    "    \n",
    "    def dfs(self, graph, color, v, c):\n",
    "        color[v] = c\n",
    "        for to in graph[v]:\n",
    "            if color[to] != 0 and color[to] == c: \n",
    "                return False\n",
    "            if color[to] == 0 and not self.dfs(graph, color, to, -c): \n",
    "                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        # 又是一道二分图的问题\n",
    "        # 又是着色问题\n",
    "        # 方法一：dfs\n",
    "        # time complexity: O(|V|+|E|), space complexity: O(|V|)\n",
    "        graph = {i:[] for i in range(1, N+1)}\n",
    "        colors = [0]*(N+1)\n",
    "        for x, y in dislikes:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        def dfs(start, c):\n",
    "            if colors[start] != 0:\n",
    "                return colors[start] == c\n",
    "            colors[start] = c\n",
    "            for neighbor in graph[start]:\n",
    "                if colors[neighbor] != -c:\n",
    "                    if not dfs(neighbor, -c):\n",
    "                        return False\n",
    "            return True\n",
    "        for i in range(1, N+1):\n",
    "            if colors[i] == 0:\n",
    "                if not dfs(i, 1):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not dislikes:return True\n",
    "        graph, had = {}, [-1] * (N + 1) \n",
    "        for i,j in dislikes:\n",
    "            if i not in graph: graph[i] = []\n",
    "            if j not in graph: graph[j] = []\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        def dfs(dis,node):\n",
    "            if had[node] != -1:\n",
    "                return (dis + had[node]) % 2 == 0\n",
    "            had[node] = dis\n",
    "            return all( dfs(dis+1, nex) for nex in graph[node] )\n",
    "        return all( dfs(0,node) for node in graph if had[node] == -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        \"\"\"\n",
    "        :type N: int\n",
    "        :type dislikes: List[List[int]]\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if not dislikes:return True\n",
    "        graph, had = {}, [-1] * (N + 1) \n",
    "        for i,j in dislikes:\n",
    "            if i not in graph: graph[i] = []\n",
    "            if j not in graph: graph[j] = []\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "        def dfs(dis,node):\n",
    "            if had[node] != -1:\n",
    "                return not (dis + had[node]) % 2\n",
    "            had[node] = dis\n",
    "            return all( dfs(dis+1, nex) for nex in graph[node] )\n",
    "        return all( dfs(0,node) for node in graph if had[node] == -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def possibleBipartition(self, N, dislikes):\n",
    "        graph = collections.defaultdict(list)\n",
    "        for u, v in dislikes:\n",
    "            graph[u].append(v)\n",
    "            graph[v].append(u)\n",
    "\n",
    "        color = {}\n",
    "        def dfs(node, c = 0):\n",
    "            if node in color:\n",
    "                return color[node] == c\n",
    "            color[node] = c\n",
    "            return all(dfs(nei, c ^ 1) for nei in graph[node])\n",
    "\n",
    "        return all(dfs(node)\n",
    "                   for node in range(1, N+1)\n",
    "                   if node not in color)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:\n",
    "        links = {i:[] for i in range(1,N+1)}\n",
    "\n",
    "        for pair in dislikes:\n",
    "            links[pair[0]].append(pair[1])\n",
    "            links[pair[1]].append(pair[0])\n",
    "\n",
    "        visited = [0]*N\n",
    "        color = {}\n",
    "\n",
    "        #ans = True\n",
    "        for i in range(1,N+1):\n",
    "            if visited[i-1] == 0:\n",
    "                visited[i-1] = 1\n",
    "                queue = [i]\n",
    "                color[i] = 0\n",
    "                #size = len(links[i])\n",
    "                while queue:\n",
    "                    init_node = queue.pop(0)\n",
    "                    size = len(links[init_node])\n",
    "                    for k in range(size):\n",
    "                        cur_node = links[init_node][k]\n",
    "                        if visited[cur_node-1] == 0:\n",
    "                            visited[cur_node-1] = 1\n",
    "                            color[cur_node] = 1-color[init_node]\n",
    "                            queue.append(cur_node)\n",
    "                        else:\n",
    "                            if color[cur_node] == color[init_node]:\n",
    "                                return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:\n",
    "        dic=defaultdict(list) # 字典表示邻接表\n",
    "        for (x,y) in dislikes:\n",
    "            dic[x].append(y)\n",
    "            dic[y].append(x)\n",
    "        hash={}\n",
    "        for i in range(1, N + 1): # 考虑图不连通的情况\n",
    "            if i not in hash:\n",
    "                static = [i]\n",
    "                hash[i] = 0\n",
    "                while static:\n",
    "                    node = static.pop()\n",
    "                    for j in dic[node]:\n",
    "                        if j not in hash:\n",
    "                            hash[j] = hash[node] ^ 1\n",
    "                            static.append(j)\n",
    "                        if hash[node] == hash[j]:\n",
    "                            return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:\n",
    "        if not dislikes: return True\n",
    "      \n",
    "\n",
    "        UNVISITED = 0\n",
    "        status =[None] + [UNVISITED] * N\n",
    "        graph = [[] for _ in range(N+1)]\n",
    "\n",
    "        for node1, node2 in dislikes:\n",
    "            graph[node1].append(node2)\n",
    "            graph[node2].append(node1)\n",
    "\n",
    "        for node in range(1,N+1):\n",
    "            if status[node] == UNVISITED:\n",
    "                status[node] = 1\n",
    "                toVisit = collections.deque([node])\n",
    "                while toVisit:\n",
    "                    cur = toVisit.popleft()\n",
    "                    for neighbor in graph[cur]:\n",
    "                        if status[neighbor] == UNVISITED:\n",
    "                            status[neighbor] = - status[cur]\n",
    "                            toVisit.append(neighbor)\n",
    "                        if status[neighbor] == status[cur]:\n",
    "                            return False\n",
    "        return True\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        clusters = []\n",
    "\n",
    "        while dislikes:\n",
    "            cur_cluster = []\n",
    "            cur_head = dislikes.pop(0)\n",
    "            cur_cluster.append(cur_head)\n",
    "            k = len(dislikes)\n",
    "            cur_all = [cur_head[0],cur_head[1]]\n",
    "            for i in range(2*k):\n",
    "                if not dislikes: break\n",
    "                if dislikes[0][0] in cur_all or dislikes[0][1] in cur_all:\n",
    "                    if dislikes[0][0] not in cur_all: cur_all.append(dislikes[0][0])\n",
    "                    if dislikes[0][1] not in cur_all: cur_all.append(dislikes[0][1])\n",
    "                    cur_cluster.append(dislikes.pop(0))\n",
    "\n",
    "                else:\n",
    "                    m = dislikes.pop(0)\n",
    "                    dislikes.append(m)\n",
    "\n",
    "            clusters.append(cur_cluster)\n",
    "\n",
    "        for cluster in clusters:\n",
    "            cur_dict = {}\n",
    "            for pair in cluster:\n",
    "                if pair[0] not in cur_dict and pair[1] not in cur_dict:\n",
    "                    cur_dict[pair[0]] = 0\n",
    "                    cur_dict[pair[1]] = 1\n",
    "                elif pair[0] not in cur_dict and pair[1] in cur_dict:\n",
    "                    cur_dict[pair[0]] = 1 - cur_dict[pair[1]]\n",
    "                elif pair[0] in cur_dict and pair[1] not in cur_dict:\n",
    "                    cur_dict[pair[1]] = 1 - cur_dict[pair[0]]\n",
    "\n",
    "                else:\n",
    "                    if cur_dict[pair[0]] == cur_dict[pair[1]]:\n",
    "                        return False\n",
    "\n",
    "        return True\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "no, g1, g2 = -1, 0, 1\n",
    "class Solution:\n",
    "    \n",
    "    def possibleBipartition(self, N: int, dislikes: List[List[int]]) -> bool:\n",
    "        if not dislikes:\n",
    "            return True\n",
    "        \n",
    "        g = defaultdict(list)\n",
    "        for i, j in dislikes:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        \n",
    "        group = [no] * (N + 1) \n",
    "        for i in range(1, N + 1):\n",
    "            if group[i] == no and not self.dfs(g, group, g1, i):\n",
    "                return False\n",
    "            \n",
    "        return True\n",
    "    \n",
    "    def dfs(self, g,gp, start, cur):\n",
    "        gp[cur] = start\n",
    "        for j in g[cur]:\n",
    "            if gp[j] == start:\n",
    "                return False\n",
    "            if gp[j] == no and not self.dfs(g, gp, 1 - start, j):\n",
    "                return False\n",
    "        \n",
    "        return True\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Person:\n",
    "    def __init__(self):\n",
    "        self.groupid = -1\n",
    "        self.dislike = []\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        if len(dislikes) < 2:\n",
    "            return True\n",
    "\n",
    "        pers = [Person() for _ in range(n)]\n",
    "        que = collections.deque()\n",
    "        #sPid, sdislikeNum = 0, 0\n",
    "        while dislikes:\n",
    "            a, b = dislikes.pop()\n",
    "            pers[a - 1].dislike.append(b - 1)\n",
    "            pers[b - 1].dislike.append(a - 1)\n",
    "\n",
    "        def Partion():\n",
    "            nonlocal que, pers\n",
    "            while que:\n",
    "                tmp, gID = que.pop()            \n",
    "                for c in tmp:\n",
    "                    if pers[c].groupid < 0:\n",
    "                        pers[c].groupid = gID\n",
    "                        que.appendleft((pers[c].dislike, 3 - gID))\n",
    "                    elif pers[c].groupid != gID:\n",
    "                        return False\n",
    "            return True\n",
    "\n",
    "        #pers[sPid].groupid = 1\n",
    "        #que.append((pers[sPid].dislike, 2))\n",
    "        \n",
    "        for p in pers:\n",
    "            if p.groupid < 0 and not p.dislike:\n",
    "                p.groupid = 1\n",
    "            else: \n",
    "                que.appendleft((p.dislike, 3 - p.groupid))\n",
    "                if not Partion():\n",
    "                    return False\n",
    "        \n",
    "        return True\n",
    "\n",
    "                 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef possibleBipartition(self,n,dislikes):\n",
    "\t\tg=[[] for _ in range(n)]\n",
    "\t\tfor x,y in dislikes:\n",
    "\t\t\tg[x-1].append(y-1)\n",
    "\t\t\tg[y-1].append(x-1)\n",
    "\t\tcolor=[0]*n\n",
    "\t\tfor i,c in enumerate(color):\n",
    "\t\t\tif c==0:\n",
    "\t\t\t\tq=deque([i])\n",
    "\t\t\t\tcolor[i]=1\n",
    "\t\t\t\twhile q:\n",
    "\t\t\t\t\tx=q.popleft()\n",
    "\t\t\t\t\tfor y in g[x]:\n",
    "\t\t\t\t\t\tif color[y]==color[x]:\n",
    "\t\t\t\t\t\t\treturn False\n",
    "\t\t\t\t\t\tif color[y]==0:\n",
    "\t\t\t\t\t\t\tcolor[y]=-color[x]\n",
    "\t\t\t\t\t\t\tq.append(y)\n",
    "\t\t\t\t#只有串联在一起的关系才有可能导致\n",
    "\t\t\t\t#别的没有问题\n",
    "\t\treturn True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Dsu:\n",
    "    def __init__(self, size):\n",
    "        self.pa = list(range(size))\n",
    "        self.size = [1] * size\n",
    "    def find(self, x):\n",
    "        return x if self.pa[x] == x else self.find(self.pa[x])\n",
    "    def union(self, x, y):\n",
    "        x, y = self.find(x), self.find(y)\n",
    "        if x == y:\n",
    "            return\n",
    "        if self.size[x] < self.size[y]:\n",
    "            x, y = y, x\n",
    "        self.pa[y] = x\n",
    "        self.size[x] += self.size[y]\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        if len(dislikes) <= 1:\n",
    "            return True\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in dislikes:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "\n",
    "        uf = Dsu(n)\n",
    "        for x, nodes in enumerate(g):\n",
    "            for y in nodes:\n",
    "                uf.union(nodes[0], y)\n",
    "                if uf.find(x) == uf.find(y):\n",
    "                    return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/env python\n",
    "# -*- coding: utf-8 -*-\n",
    "#  Copyright © Huawei Technologies Co., Ltd. 2020. All rights reserved.\n",
    "\n",
    "# @Time    : 2023/03/27\n",
    "# @File    : 可能的二分法-886.py\n",
    "# @Software: WeAutomate\n",
    "\n",
    "\"\"\"\n",
    "给定一组 n 人（编号为 1, 2, ..., n）， 我们想把每个人分进任意大小的两组。每个人都可能不喜欢其他人，那么他们不应该属于同一组。\n",
    "\n",
    "给定整数 n 和数组 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允许将编号为 ai 和  bi的人归入同一组。当可以用这种方法将所有人分进两组时，返回 true；否则返回 false。\n",
    "\n",
    "\n",
    "\n",
    "示例 1：\n",
    "\n",
    "输入：n = 4, dislikes = [[1,2],[1,3],[2,4]]\n",
    "输出：true\n",
    "解释：group1 [1,4], group2 [2,3]\n",
    "示例 2：\n",
    "\n",
    "输入：n = 3, dislikes = [[1,2],[1,3],[2,3]]\n",
    "输出：false\n",
    "示例 3：\n",
    "\n",
    "输入：n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]\n",
    "输出：false\n",
    "\n",
    "\n",
    "提示：\n",
    "\n",
    "1 <= n <= 2000\n",
    "0 <= dislikes.length <= 104\n",
    "dislikes[i].length == 2\n",
    "1 <= dislikes[i][j] <= n\n",
    "ai < bi\n",
    "dislikes 中每一组都 不同\n",
    "\n",
    "\"\"\"\n",
    "\n",
    "class Solution():\n",
    "    def possibleBipartition(self, n, dislikes):\n",
    "        \"\"\"\n",
    "\n",
    "        :param n:\n",
    "        :param dislikes:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        if n < 2:\n",
    "            return True\n",
    "        color = [None for _ in range(n)]\n",
    "        # dislikes = sorted(dislikes, key=lambda x: (x[0], x[1]))\n",
    "        color[dislikes[0][0]-1] = True\n",
    "        flag = False\n",
    "\n",
    "        while dislikes:\n",
    "            remove_dislikes = []\n",
    "\n",
    "            for n1, n2 in dislikes:\n",
    "                if color[n1 - 1] is None and color[n2 - 1] is None:\n",
    "                    continue\n",
    "                if color[n1 - 1] is not None and color[n2 - 1] is not None:\n",
    "                    if color[n1 - 1] == color[n2-1]:\n",
    "                        return False\n",
    "                if color[n1 - 1] is not None:\n",
    "                    color[n2 - 1] = not color[n1 - 1]\n",
    "                    remove_dislikes.append([n1, n2])\n",
    "                    flag = True\n",
    "                else:\n",
    "                    color[n1 - 1] = not color[n2 - 1]\n",
    "                    remove_dislikes.append([n1, n2])\n",
    "                    flag = True\n",
    "            for dis in remove_dislikes:\n",
    "                dislikes.remove(dis)\n",
    "            if not dislikes:\n",
    "                return True\n",
    "            #\n",
    "            if not flag:\n",
    "                color[dislikes[0][0] - 1] = True\n",
    "            flag = False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        g = [[] for _ in range(n + 1)]\n",
    "        for a, b in dislikes:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        colors = [0] * (n + 1)\n",
    "        for a in range(1, n + 1):\n",
    "            if colors[a] != 0:\n",
    "                continue\n",
    "            q = deque([a])\n",
    "            colors[a] = -1\n",
    "            while q:\n",
    "                c = q.pop()\n",
    "                for d in g[c]:\n",
    "                    if colors[d] == 0:\n",
    "                        colors[d] = -colors[c]\n",
    "                        q.appendleft(d)\n",
    "                    elif colors[c] == colors[d]:\n",
    "                        return False\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        judge = [-1] * (n + 1)\n",
    "        judge[0] = 0\n",
    "        while -1 in judge:\n",
    "            queue = []\n",
    "            queue.append(judge.index(-1))\n",
    "            judge[judge.index(-1)] = 1\n",
    "            while len(queue) != 0:\n",
    "                temp = queue.pop(0)\n",
    "                for edge in dislikes:\n",
    "                    if temp in edge:\n",
    "                        if temp == edge[0]:\n",
    "                            if judge[edge[1]] == -1:\n",
    "                                if judge[edge[0]] == 1:\n",
    "                                    judge[edge[1]] = 2\n",
    "                                elif judge[edge[0]] == 2:\n",
    "                                    judge[edge[1]] = 1\n",
    "                                queue.append(edge[1])\n",
    "                            elif judge[edge[1]] != -1:\n",
    "                                if judge[edge[1]] == judge[edge[0]]:\n",
    "                                    return False\n",
    "                        elif temp == edge[1]:\n",
    "                            if judge[edge[0]] == -1:\n",
    "                                if judge[temp] == 1:\n",
    "                                    judge[edge[0]] = 2\n",
    "                                elif judge[temp] == 2:\n",
    "                                    judge[edge[0]] = 1\n",
    "                                queue.append(edge[0])\n",
    "                            elif judge[edge[0]] != -1:\n",
    "                                if judge[edge[0]] == judge[temp]:\n",
    "                                    return False\n",
    "        return True\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        if not dislikes:\n",
    "            return True\n",
    "\n",
    "        tu = defaultdict(set)\n",
    "        for a,b in dislikes:\n",
    "            tu[a].add(b)\n",
    "            tu[b].add(a)\n",
    "        group = [0]*(n+1)  # 1,-1,0\n",
    "        for index, gp in enumerate(group):\n",
    "            if gp==0:\n",
    "                group[index]=1\n",
    "                q = deque()\n",
    "                q.append(index)\n",
    "                while q:\n",
    "                    t = q.popleft()\n",
    "                    for sub in tu[t]:\n",
    "                        if group[sub]==group[t]:\n",
    "                            return False\n",
    "                        if group[sub]==0:\n",
    "                            group[sub]=-group[t]\n",
    "                            q.append(sub)\n",
    "        return True\n",
    "\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for v1, v2 in dislikes:\n",
    "            graph[v1].append(v2)\n",
    "            graph[v2].append(v1)\n",
    "\n",
    "        used = [True] + ([False] * n)\n",
    "        colors = [False] * (n + 1)\n",
    "        for node in range(1, n + 1):\n",
    "            if not self.sub(graph, used, colors, node):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def sub(self, graph, used, colors, node):\n",
    "        used[node] = True\n",
    "        for val in graph[node]:\n",
    "            if used[val]:\n",
    "                if colors[node] == colors[val]:\n",
    "                    return False\n",
    "            else:\n",
    "                colors[val] = not colors[node]\n",
    "                self.sub(graph, used, colors, val)\n",
    "        return True\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def __init__(self):\n",
    "#         self.ok = True\n",
    "#         self.color = None\n",
    "#         self.visited = None\n",
    "#     def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "#         # 图节点编号从 1 开始\n",
    "#         self.color = [False] * (n + 1)\n",
    "#         self.visited = [False] * (n + 1)\n",
    "#         # 转化成邻接表表示图结构\n",
    "#         graph = self.buildGraph(n, dislikes)\n",
    "#         for v in range(1, n+1):\n",
    "#             if not self.visited[v]:\n",
    "#                 self.traverse(graph, v)\n",
    "#         return self.ok\n",
    "#     # 建图函数\n",
    "#     def buildGraph(self, n: int, dislikes: List[List[int]]) -> List[List[int]]:\n",
    "#         # 图节点编号为 1...n\n",
    "#         graph = [[] for _ in range(n + 1)]\n",
    "#         for edge in dislikes:\n",
    "#             v = edge[1]\n",
    "#             w = edge[0]\n",
    "#             # 「无向图」相当于「双向图」\n",
    "#             # v -> w\n",
    "#             graph[v].append(w)\n",
    "#             # w -> v\n",
    "#             graph[w].append(v)\n",
    "#         return graph\n",
    "#     # 和之前判定二分图的 traverse 函数完全相同\n",
    "#     def traverse(self, graph: List[List[int]], v: int) -> None:\n",
    "#         if not self.ok:\n",
    "#             return\n",
    "#         self.visited[v] = True\n",
    "#         for w in graph[v]:\n",
    "#             if not self.visited[w]:\n",
    "#                 self.color[w] = not self.color[v]\n",
    "#                 self.traverse(graph, w)\n",
    "#             else:\n",
    "#                 if self.color[w] == self.color[v]:\n",
    "#                     self.ok = False\n",
    "\n",
    "# # 并查集\n",
    "# class Solution:\n",
    "#     def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "#         def find(x):\n",
    "#             if p[x] != x:\n",
    "#                 p[x] = find(p[x])\n",
    "#             return p[x]\n",
    "#         g = collections.defaultdict(list)\n",
    "#         for a, b in dislikes:\n",
    "#             a, b = a - 1, b - 1\n",
    "#             g[a].append(b)\n",
    "#             g[b].append(a)\n",
    "#         p = list(range(n))\n",
    "#         for i in range(n):\n",
    "#             for j in g[i]:\n",
    "#                 if find(i) == find(j):\n",
    "#                     return False\n",
    "#                 p[find[j]] = find(g[i][0])\n",
    "#         return True\n",
    "\n",
    "# 并查集+影子分身[另加反面影子分身，x -> x+n，再与影子组队拉串。只需一次扫描。这思路很特别]\n",
    "# class Solution:\n",
    "#     def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "#         def find(x):\n",
    "#             if p[x] != x:\n",
    "#                 p[x] = find(p[x])   #拉串，找到并设置队头(老大)\n",
    "#             return p[x]\n",
    "#         p = list(range(n*2+1))  #拉串用的队组标识，另加反面影子分身\n",
    "#         for i, j in dislikes:\n",
    "#             if find(i) == find(j):\n",
    "#                 return False\n",
    "#             p[find(j)] = find(i + n)    #与影子组队拉串\n",
    "#             p[find(i)] = find(j + n)    #与影子组队拉串\n",
    "#             # p[find(j)] = p[find(i + n)]    #与影子组队拉串    上下两种方式都可以\n",
    "#             # p[find(i)] = p[find(j + n)]    #与影子组队拉串\n",
    "#         return True\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, ds: List[List[int]]) -> bool:\n",
    "        p = [i for i in range(0, 2 * n + 10)]\n",
    "        def find(x):\n",
    "            if p[x] != x:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "        def union(a, b):\n",
    "            p[find(a)] = find(b)\n",
    "        def query(a, b):\n",
    "            return find(a) == find(b)\n",
    "        for info in ds:\n",
    "            a, b = info[0], info[1]\n",
    "            if query(a, b):\n",
    "                return False\n",
    "            else:\n",
    "                union(a, b + n)\n",
    "                union(b, a + n)\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        # 相当于每条边的两个点必须为不同集合\n",
    "        edges = dict()\n",
    "        for i in range(1, 2001):\n",
    "            edges[i] = []\n",
    "        \n",
    "        for edge in dislikes:\n",
    "            edges[edge[0]].append(edge[1])\n",
    "            edges[edge[1]].append(edge[0])\n",
    "        \n",
    "        seen = [0] * 2001\n",
    "        for st in range(1, 2001):\n",
    "            if seen[st] != 0 or len(edges[st]) == 0:\n",
    "                continue\n",
    "            \n",
    "            que = deque()\n",
    "            que.append(st)\n",
    "            seen[st] = 1\n",
    "            while len(que) > 0:\n",
    "                cur = que.popleft()\n",
    "                for to in edges[cur]:\n",
    "                    if seen[to] == 0:\n",
    "                        que.append(to)\n",
    "                        seen[to] = 1 if seen[cur] == 2 else 2\n",
    "                    elif seen[to] == seen[cur]:\n",
    "                        return False\n",
    "        \n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        visited = [False] * n\n",
    "        color = [False] * n\n",
    "\n",
    "        for edge in dislikes:\n",
    "            n1, n2 = edge[0] - 1, edge[1] -1\n",
    "            if n2 not in graph[n1]:\n",
    "                graph[n1].append(n2)\n",
    "            if n1 not in graph[n2]:\n",
    "                graph[n2].append(n1)\n",
    "        print(graph)\n",
    "\n",
    "        for start in range(n):\n",
    "            if visited[start]:\n",
    "                continue\n",
    "\n",
    "            q = [start]\n",
    "            visited[start] = True\n",
    "            while q:\n",
    "                cur = q.pop(0)\n",
    "                for child in graph[cur]:\n",
    "                    if not visited[child]:\n",
    "                        color[child] = not color[cur]\n",
    "                        visited[child] = True\n",
    "                        q.append(child)\n",
    "                    else:\n",
    "                        if color[child] == color[cur]:\n",
    "                            return False\n",
    "        return True\n",
    "\n",
    "        \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# https://labuladong.github.io/algo/di-yi-zhan-da78c/shou-ba-sh-03a72/er-fen-tu--73400/#%E9%A2%98%E7%9B%AE%E5%AE%9E%E8%B7%B5\n",
    "# 其实这题考察的就是二分图的判定\n",
    "# 那就回到了「双色问题」，如果能够用两种颜色着色所有节点，且相邻节点颜色都不同，那么你按照颜色把这些节点分成两组不就行了嘛\n",
    "\n",
    "# 无向图：自己要构建图。不像785题，虽然也是无向图，但是例子中给出了图的画法，跟题目中给出的列表是对应的。相当于图已经被构建出来了\n",
    "# 本题目的意思就是判定是否是二分图。\n",
    "# 题目中给出的编号是1到n。无向图相当于是双向图\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.ok = True\n",
    "        self.visited = None\n",
    "        self.color = None\n",
    "\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        # idx为0的相当于是占位符\n",
    "        # 图节点编号从 1 开始\n",
    "        self.visited = [False] * (n+1)\n",
    "        self.color = [False] * (n+1)\n",
    "\n",
    "        # 转化成邻接表表示图结构\n",
    "        graph = self.buildGraph(n, dislikes)\n",
    "\n",
    "        for v in range(1, n+1):\n",
    "            if not self.visited[v]:\n",
    "                self.traverse(graph, v)\n",
    "        \n",
    "        return self.ok\n",
    "    \n",
    "    # 建图函数\n",
    "    def buildGraph(self, n, dislikes):\n",
    "        # 图节点编号为 1...n\n",
    "        graph = [[] for _ in range(n+1)]\n",
    "\n",
    "        for w, v in dislikes:\n",
    "            # 「无向图」相当于「双向图」\n",
    "            # v -> w\n",
    "            graph[w].append(v)\n",
    "            graph[v].append(w)\n",
    "        \n",
    "        return graph\n",
    "\n",
    "    # 和之前判定二分图的 traverse 函数完全相同\n",
    "    def traverse(self, graph, s):\n",
    "        if not self.ok:\n",
    "            return\n",
    "        \n",
    "        self.visited[s] = True\n",
    "        for w in graph[s]:\n",
    "            if not self.visited[w]:\n",
    "                self.color[w] = not self.color[s]\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                if self.color[w] == self.color[s]:\n",
    "                    self.ok = False\n",
    "                    return\n",
    "                else:\n",
    "                    continue\n",
    "        \n",
    "    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        graph = [[] for i in range(n+1)]\n",
    "        for i in dislikes:\n",
    "            graph[i[0]].append(i[1])\n",
    "            graph[i[1]].append(i[0])\n",
    "        \n",
    "        self.ok = True\n",
    "        self.visited = [False]*(n+1)\n",
    "        self.color = [False]*(n+1)\n",
    "\n",
    "        for i in range(1, n+1):\n",
    "            if not self.visited[i]:\n",
    "                self.traverse(graph, i)\n",
    "                if not self.ok:\n",
    "                    return self.ok \n",
    "        \n",
    "        return self.ok\n",
    "\n",
    "    def traverse(self, graph, v):\n",
    "        self.visited[v] = True \n",
    "        for w in graph[v]:\n",
    "            if not self.visited[w]:\n",
    "                self.color[w] = not self.color[v]\n",
    "                self.traverse(graph, w)\n",
    "            else:\n",
    "                if self.color[w] == self.color[v]:\n",
    "                    self.ok = False \n",
    "                    return "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        # 以dislikes为边，判断是否能构建二分图\n",
    "        self.visited = [False] * (n + 1)\n",
    "        self.attrs = [1] * (n + 1)\n",
    "        self.res = True\n",
    "        \n",
    "        # build graph\n",
    "        self.graph = [[] for _ in range(n + 1)]\n",
    "        for a, b in dislikes:\n",
    "            self.graph[a].append(b)\n",
    "            self.graph[b].append(a)\n",
    "\n",
    "        for idx in range(1, n+1):\n",
    "            if not self.res:\n",
    "                return self.res\n",
    "            if not self.visited[idx]:\n",
    "                self.judge_binary_graph(idx)\n",
    "        return self.res\n",
    "\n",
    "    def judge_binary_graph(self, idx):\n",
    "        if self.visited[idx]:\n",
    "            return\n",
    "\n",
    "        self.visited[idx] = True\n",
    "        for nei in self.graph[idx]:\n",
    "            if not self.visited[nei]:\n",
    "                self.attrs[nei] = -1 * self.attrs[idx]\n",
    "                self.judge_binary_graph(nei)\n",
    "            else:\n",
    "                if self.attrs[nei] == self.attrs[idx]:\n",
    "                    self.res = False\n",
    "                    return"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in dislikes:\n",
    "            graph[x-1].append(y-1)\n",
    "            graph[y-1].append(x-1)\n",
    "        color = [-1] * n\n",
    "        def dfs(u, c):\n",
    "            color[u] = c\n",
    "            for v in graph[u]:\n",
    "                if color[v] == -1: # 未染色\n",
    "                    if not dfs(v, c^1):  # 染相反颜色但失败\n",
    "                        return False\n",
    "                if color[v] == c: return False  # 相同颜色，失败\n",
    "            return True \n",
    "        for i in range(n):  # 图不一定连通\n",
    "            if color[i] == -1:\n",
    "                if not dfs(i, 0): return False\n",
    "        return True\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        # 染色法\n",
    "        Map = {}\n",
    "        # 双向建图\n",
    "        for st,end in dislikes:\n",
    "            if st in Map:\n",
    "                Map[st].append(end)\n",
    "            else:\n",
    "                Map[st] = [end]\n",
    "            if end in Map:\n",
    "                Map[end].append(st)\n",
    "            else:\n",
    "                Map[end] = [st]\n",
    "\n",
    "        # 从某点开始染色，看看是不是满足情况\n",
    "        # 将n点染成c颜色\n",
    "        color = [0]*(n+1)\n",
    "        \n",
    "        def dfs(n):\n",
    "            if n in Map:\n",
    "                for i in Map[n]:\n",
    "                    if color[i] == 0:\n",
    "                        # 向下递归\n",
    "                        color[i] = -color[n]\n",
    "                        if not dfs(i):\n",
    "                            return False \n",
    "                    else:\n",
    "                        if color[i] == color[n]:\n",
    "                            return False \n",
    "                return True \n",
    "            else:\n",
    "                return True \n",
    "\n",
    "        for i in range(1,n+1):\n",
    "            if color[i] == 0:\n",
    "                color[i] = 1\n",
    "                if not dfs(i):\n",
    "                    return False    \n",
    "        return True "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for dis in dislikes:\n",
    "            #无向图是双向的\n",
    "            graph[dis[1]].append(dis[0])\n",
    "            graph[dis[0]].append(dis[1])\n",
    "        #长度\n",
    "        visited = [False] * (n + 1)\n",
    "        colored = [False] * (n + 1)\n",
    "        self.group = True\n",
    "\n",
    "        def dfs(node):\n",
    "            if not self.group:\n",
    "                return \n",
    "            visited[node] = True\n",
    "            for neighbor in graph[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    colored[neighbor] = not colored[node]\n",
    "                    dfs(neighbor)\n",
    "                else:\n",
    "                    if colored[neighbor] == colored[node]:\n",
    "                        self.group = False\n",
    "                        return\n",
    "        #记住这里是in range (length)因为是要把每一个没标记的visited里的dfs跑一遍\n",
    "        for node in range(n + 1):\n",
    "            if not visited[node]:\n",
    "                dfs(node)\n",
    "        return self.group\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        graph = [[] for _ in range(n + 1)]\n",
    "        for dis in dislikes:\n",
    "            #无向图是双向的\n",
    "            graph[dis[1]].append(dis[0])\n",
    "            graph[dis[0]].append(dis[1])\n",
    "        #长度\n",
    "        visited = [False] * (n + 1)\n",
    "        colored = [False] * (n + 1)\n",
    "        self.group = True\n",
    "\n",
    "        def dfs(node):\n",
    "            if not self.group:\n",
    "                return \n",
    "            visited[node] = True\n",
    "            for neighbor in graph[node]:\n",
    "                if not visited[neighbor]:\n",
    "                    colored[neighbor] = not colored[node]\n",
    "                    dfs(neighbor)\n",
    "                else:\n",
    "                    if colored[neighbor] == colored[node]:\n",
    "                        self.group = False\n",
    "                        return\n",
    "        #记住这里是in range (length)因为是要把每一个没标记的visited里的dfs跑一遍\n",
    "        for node in range(n + 1):\n",
    "            if not visited[node]:\n",
    "                dfs(node)\n",
    "        return self.group\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        visited = [0]*n\n",
    "        color= [0]*n #颜色0 1  两个组\n",
    "        grapg = collections.defaultdict(list)\n",
    "        for people in dislikes:\n",
    "            grapg[people[0]-1].append(people[1]-1)\n",
    "            grapg[people[1]-1].append(people[0]-1)\n",
    "\n",
    "        def dfs(u: int, clo: int) -> bool:\n",
    "            #能否成功的给子节点染色\n",
    "            if visited[u] == 1 and color[u] ==clo :\n",
    "                return  True\n",
    "            if visited[u] == 1 and  color[u] !=clo:\n",
    "                return False\n",
    "            visited[u] = 1\n",
    "            color[u] = clo\n",
    "            for nextD in grapg[u]:\n",
    "                if not dfs(nextD, 1-clo):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        \n",
    "        for i in range(0,n): #从1到n 人 对应 0->n-1\n",
    "            if visited[i] == 0:\n",
    "                if not dfs(i,0):\n",
    "                    return False\n",
    "        return True\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        def dfs(i, c):\n",
    "            color[i] = c\n",
    "            for j in g[i]:\n",
    "                if color[j] == c:\n",
    "                    return False\n",
    "                if color[j] == 0 and not dfs(j, 3 - c):\n",
    "                    return False\n",
    "            return True\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        color = [0] * n\n",
    "        for a, b in dislikes:\n",
    "            a, b = a - 1, b - 1\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        return all(c or dfs(i, 1) for i, c in enumerate(color))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in dislikes:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        color = [0] * n  # color[x] = 0 表示未访问节点 x\n",
    "        def dfs(x: int, c: int) -> bool:\n",
    "            color[x] = c\n",
    "            return all(color[y] != c and (color[y] or dfs(y, -c)) for y in g[x])\n",
    "        return all(c or dfs(i, 1) for i, c in enumerate(color))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def possibleBipartition(self, n: int, dislikes: List[List[int]]) -> bool:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in dislikes:\n",
    "            g[x - 1].append(y - 1)\n",
    "            g[y - 1].append(x - 1)\n",
    "        color = [0] * n  # color[x] = 0 表示未访问节点 x\n",
    "        def dfs(x: int, c: int) -> bool:\n",
    "            color[x] = c\n",
    "            return all(color[y] != c and (color[y] or dfs(y, -c)) for y in g[x])\n",
    "        return all(c or dfs(i, 1) for i, c in enumerate(color))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
